
using llt = long long;
using vi = vector<llt>;
llt const MOD = 1E9 + 7;

class Solution {
public:
    int numberOfWays(int n, int x) {
        vi vec;
        vec.emplace_back(1);
        for(int i=2;i<=n;++i){
            llt k = 1;
            for(int j=0;j<x;++j) k *= i; 
            if(k > n) break;
            vec.emplace_back(k);
        }

        vi D(n + 1, 0);
        D[0] = 1;
        for(auto i : vec)for(int v=n;v>=i;--v){
            (D[v] += D[v - i]) %= MOD;
        }
        return D[n];
    }
};